فلما كانت عمرة القضاء تغيب فيمن تغيب من المشركين كراهة رؤية المسلمين وهم بمكة ، فسأل رسول اللّه صلى اللّه عليه وسلم عنه أخاه الوليد بن الوليد ، وتعجب كيف يغيب الإسلام عن مثل خالد ، فكتب له أخوه هذا الكتاب : ( بسم اللّه الرحمن الرحيم ، فإني لم أر أعجب من ذهاب رأيك عن الإسلام ، وعقلك عقلك ! ! ومثل الإسلام جهله أحد ؟ ! وقد سألني رسول اللّه عنك وقال : « أين خالد » ؟ فقلت : يأتي اللّه به فقال : « مثله جهل الإسلام ؟ ولو كان جعل نكايته وجدّه مع المسلمين كان خيرا له ، ولقدّمناه على غيره » ، فاستدرك يا أخي ما قد فاتك من مواطن صالحة ) . فلما وصل خالدا الكتاب وقع سؤال النبي عنه من نفسه ، واستشعر ما فيه من معان وتقدير كريم ، فازداد رغبة في الإسلام ، وقوّى هذه الرغبة في نفسه رؤيا رآها : رأى أنه كان في بلاد ضيقة مجدبة ، فخرج منها إلى بلاد خضراء واسعة ، فقال : إن هذه لرؤيا ! ! فكانت البلاد الضيقة - كما عبّرها له الصدّيق فيما بعد - هي دنيا الشرك الذاهبة القاحلة . وكانت البلاد الخضراء الواسعة هي دنيا الإسلام الفسيحة الخصبة . وأدركته لحظة من لحظات التجلّي الإلهي ، فعزم على الخروج إلى رسول اللّه ، وعرض هذه الفكرة على صفوان بن أمية وعكرمة بن أبي جهل فأبيا ، ثم عرضها على عثمان بن طلحة فأسرع الإجابة . وخرج خالد وعثمان حتى كانا بالطريق بين مكة والمدينة التقيا بعمرو بن العاص ، فقال له : أين يا أبا سليمان - يعني خالدا - ؟ قال : واللّه لقد استقام الميسم - أي تبين الطريق ووضح - وإن الرجل لنبي ، أذهب - واللّه - فأسلم ، فحتى متى ؟ ! وسار الركب الميمون المبارك حتى دخلوا المدينة ، فأصلحوا من شأنهم ولبسوا صالح ثيابهم ، ثم قصدوا إلى النبي . وكان البشير قد جاء بالبشرى إلى رسول اللّه فسر بمقدمهم ، ولقيهم أخوه الوليد فقال لخالد : أسرع فإن رسول اللّه صلى اللّه عليه وسلم قد سر بمقدمك وهو ينتظركم ، فأسرعوا حتى وقفوا على الرسول